/************************************************** 
  函数功能：对数组快速排序                        
  函数参数：指向整型数组arr的首指针arr；           
          整型变量left和right左右边界的下标    
  函数返回值：空                                   
/**************************************************/  
void QuickSort(int *arr, int left, int right)  
{  
  int i,j;  
  if(left < right)  
  {  
    i = left; 
    j = right;  
    arr[0] = arr[i]; //准备以本次最左边的元素值为标准进行划分，先保存其值  
    do  
    {  
      while(arr[j] > arr[0] && i < j)   
        j--;        //从右向左找第1个小于标准值的位置j  
      if(i < j)     //找到了，位置为j  
      {   
        arr[i] = arr[j];  
        i++;  
      }           //将第j个元素置于左端并重置i  
      while(arr[i] < arr[0] && i < j)  
        i++;      //从左向右找第1个大于标准值的位置i  
      if(i < j)   //找到了，位置为i  
      {   
        arr[j] = arr[i];  
        j--;  
      }           //将第i个元素置于右端并重置j  
    }while(i != j);  
    arr[i] = arr[0];                //将标准值放入它的最终位置,本次划分结束  
    QuickSort(arr, left, i-1);      //对标准值左半部递归调用本函数  
    QuickSort(arr, i+1, right);     //对标准值右半部递归调用本函数  
  }  
}  

int Partition(int* input, int n, int start, int end)
{
  return 0;  
}

void GetLeastNumbers_by_partition(int* input, int n, int* output, int k)  
{  
    if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)  
        return;  
    int start = 0;  
    int end = n - 1;  
    int index = Partition(input, n, start, end);  
    while(index != k - 1)  
    {  
        if(index > k - 1)  
        {  
            end = index - 1;  
            index = Partition(input, n, start, end);  
        }  
        else  
        {  
            start = index + 1;  
            index = Partition(input, n, start, end);  
        }  
    }  
    for(int i = 0; i < k; ++i)  
        output[i] = input[i];  
} 
